The invention relates to Parallel (Turbo codes) or Serial Concatenated Convolutional codes. More specifically, the invention relates to interleavers for parallel or serial concatenated convolutional codes.
Both parallel and serial concatenated convolutional codes are referred to herein as Turbo codes for simplicity. Several techniques for using interleaving for Turbo codes have been addressed in the prior art. A random interleaver is the most common interleaver design for Turbo codes. A random interleaver of length N selects random integers between 1 and N for a block of data of length N, i.e., the random interleaver is a permutation of N integers that, for each i, there is a corresponding random integer xcfx80(i), without repetition. For large values of N, most random interleavers perform well. However, when the interleaver block size decreases, the performance of the Turbo codes degrades substantially up to a point that its BER performance is worse than the convolutional codes with similar computational complexity. Most random interleavers demonstrate an acceptable bit error rate (BER) performance; however, research has been conducted to design interleavers for Turbo codes that can outperform random interleavers.
One approach was introduced in xe2x80x9cWeight Distributions for Turbo Codes Using Random and Nonrandom Permutations,xe2x80x9d by S. Benedetto, D. Divsalar, G. Montorsi and F. Pollara, TDA Report p. 42-122, Aug. 15, 1995, wherein the interleaver was called an S_random interleaver. In this approach, for each integer i, where 1xe2x89xa6ixe2x89xa6N, a random number is chosen between 1 and N that maps the i-th bit to a new location in the interleaver. When a value is chosen, the value is compared to the S previously selected integers. If the current selection is equal to any of S previous selections within a distance xc2x1S, then the current selection is rejected. Any selected integer should be chosen only once in the interleaver. The process repeats until all N integers are selected in a random order. Computer simulation results have shown that if Sxe2x89xa6{square root over (N/2)}, then the process will converge. This interleaver design assures that the short cycle events are avoided. A short cycle event occurs when two bits are close to each other before and after interleaving. This approach was considered to provide the best interleaver for Turbo codes for a long time, especially for short block length interleavers.
Recently, a new approach was developed that is based on the S random interleaver, but that also attempts to maximize the minimum effective free distance of the code. The new approach, described in xe2x80x9cCombined Turbo Codes and Interleaver Design,xe2x80x9d by J. Yuan, B. Vucetic and W. Feng, IEEE Trans.on Communication, Vol. 47, No. 4, April, 1999, not only selects the integers in the interleaver based on the S_random criteria, but also attempts to provide an interleaver with a minimum effective free distance that is larger than a preselected value.
A new interleaver design was recently proposed by J. Hokfelt, O. Edfors, and T. Maseng, xe2x80x9cTurbo Codes: Correlated Extrinsic Information and its Impact on Iterative Decoding Performance,xe2x80x9d Proceeding of IEEE VTC ""99, Houston, Tex., based on the performance of iterative decoding algorithm in Turbo codes. Turbo codes utilize an iterative decoding algorithm based on a MAP algorithm (described by L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, xe2x80x9cOptimum decoding of linear codes for minimizing symbol error rate,xe2x80x9d IEEE Trans. On Inf. Theory, vol. IT-20, pp. 284-287, Mar. 1974, and hereby incorporated by reference) or any algorithm that provides soft output. At each decoding step, some information related to the parity bits of one decoder is fed into the next decoder together with the systematic data sequence and the parity bits corresponding to that decoder, as is known by those skilled in the art of using turbo codes. The inputs to each decoder are input data sequence dk, the parity bits y1k or y2k, and the logarithm of likelihood ratio (LLR) associated with the parity bits from the other decoder (W1k or W2k). All these inputs are utilized by the MAP decoder to create three outputs corresponding to the weighted versions of these inputs. The output {circumflex over (d)}k of the first decoder represents the weighted version of the input data sequence dk. Also, the input data sequence is fed into the second decoder after interleaving. The input to each decoder from the other decoder is used as a priori probability in the next decoding step. This information is more effective in the performance of the iterative decoding when it is less correlated to the input data sequence (or interleaved input data sequence). Thus, this criterion is used for designing the interleaver. For large block interleavers, most random interleavers provide a low correlation between Wik and the input data sequence dk. The correlation coefficient rWk11,dk21 is defined as the correlation coefficient between Wik and dk2. J. Hokfelt, O. Edfors, and T. Maseng, xe2x80x9cTurbo Codes: Correlated Extrinsic Information and its Impact on Iterative Decoding Performance,xe2x80x9d Proceeding of IEEE VTC ""99, Houston, Tex., have shown that rWk11,dk21 can be analytically approximated as                                           r            ^                                              W                              k                1                            1                        ,                          d                              k                2                                              1                =                  {                                                                      a                  ⁢                                      xe2x80x83                                    ⁢                                      exp                                                                                                                        -                            c                                                    ⁢                                                      "LeftBracketingBar"                                                          k1                              -                              k2                                                        "RightBracketingBar"                                                    ⁢                                                      xe2x80x83                                                    ⁢                          if                          ⁢                                                      xe2x80x83                                                    ⁢                          k1                                                ≠                        k2                                            "RightBracketingBar"                                                                                                                    xe2x80x83                                                                                    0                                                                                  if                    ⁢                                          xe2x80x83                                        ⁢                    k1                                    =                  k2                                                                                        (        1        )            
where a and c are two constants that depend on the encoder feedback and feedforward polynomials. The correlation coefficient at the output of the second decoder is approximated as
{circumflex over (r)}W2,d2=xc2xd{circumflex over (r)}W1,d1P(I+{circumflex over (r)}W1,d1)xe2x80x83xe2x80x83(2)
where the two terms on the right hand side of (2) correspond to the correlation coefficients between W2 and the two input data, i.e., W1 and d. Similar correlation coefficients can be computed regarding the de-interleaver. The correlation matrix corresponding to the de-interleaver {circumflex over (r)}xe2x80x2W2,d2 is the same as (2), except P is substituted by
Then Vk1, which is the variance of the correlation coefficients, is defined as                               V                      k            1                          =                              1                          N              -              1                                ⁢                                    ∑                                                k                  2                                =                1                            N                        ⁢                                          (                                                                            r                      ^                                                                                      W                                                  k                          1                                                2                                            ,                                              d                                                  k                          2                                                                                      2                                    -                                                                                    r                        ^                                            _                                                              W                      ,                                              d                                                  k                          2                                                                                      2                                                  )                            2                                                          (        3        )            
where                                                         r              ^                        _                                W            ,                          d                              k                2                                              2                =                              1                          N              -              1                                ⁢                                    ∑                                                k                  2                                =                1                            N                        ⁢                                          r                ^                                                              W                                      k                    1                                    2                                ,                                  d                                      k                    2                                                              2                                                          (        4        )            
Vxe2x80x2k1 is defined similarly using {circumflex over (r)}xe2x80x2W2,d2.
The iterative decoding suitability (IDS) measure is then defined as                     IDS        =                              1                          2              ⁢              N                                ⁢                                    ∑                                                k                  1                                =                1                            N                        ⁢                          (                                                V                                      k                    1                                                  +                                  V                                      k                    1                                    xe2x80x2                                            )                                                          (        5        )            
A low value of IDS is an indication that correlation properties between W1 and d are equally spread along the data sequence of length N. An interleaver design based on the IDS condition is suggested by J. Hokfelt, O. Edfors, and T. Maseng, xe2x80x9cInterleaver Design for Turbo Codes Based on the Performance of Iterative Decoding,xe2x80x9d Proceeding of IEEE ICC ""99, Vancouver, Canada.
However, there is a need for a more efficient S_random interleaver.
The current invention is based on two optimization criteria using an S_random interleaver. The first criterion is to maximize the distance spectrum properties of the code by designing an interleaver that increases the minimum effective free distance of the code. The second criterion is to design the interleaver in a way to reduce the correlation properties of the extrinsic information that is fed into the next stage decoder. The present invention utilizes different techniques to achieve these two properties based on a S_random interleaver. This design maximizes the bit error rate (BER) performance of the code with respect to iterative decoding in Turbo codes.